# 1658. 将 x 减到 0 的最小操作数

# 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

# 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

#  

# 示例 1：

# 输入：nums = [1,1,4,2,3], x = 5
# 输出：2
# 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
# 示例 2：

# 输入：nums = [5,6,7,8,9], x = 4
# 输出：-1
# 示例 3：

# 输入：nums = [3,2,20,1,1,3], x = 10
# 输出：5
# 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
#  

# 提示：

# 1 <= nums.length <= 105
# 1 <= nums[i] <= 104
# 1 <= x <= 109


# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

from time import time
from typing import List


class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        #  官解，计算 len(nums) 次去找最小次数
        n = len(nums)
        total = sum(nums)

        if total < x:
            return -1
        
        right = 0
        lsum, rsum = 0, total
        ans = n + 1
        for left in range(-1, n - 1):
            if left != -1:
                lsum += nums[left]
            while right < n and lsum + rsum > x:
                rsum -= nums[right]
                right += 1
            if lsum + rsum == x:
                ans = min(ans, (left + 1) + (n - right))
        
        return -1 if ans > n else ans
     
        
if __name__ == '__main__':
    start = time()
    a = Solution()
    print(a.minOperations(nums = [1,1,4,2,3], x = 5))
    print(a.minOperations(nums = [5,6,7,8,9], x = 4))
    print(a.minOperations(nums = [3,2,20,1,1,3], x = 10))
    print(a.minOperations(nums = [5,2,3,1,1], x = 5))
    print(a.minOperations(nums = [1,1], x = 3))
    print(a.minOperations(nums = [6016,5483,541,4325,8149,3515,7865,2209,9623,9763,4052,6540,2123,2074,765,7520,4941,5290,5868,6150,6006,6077,2856,7826,9119], x = 31841))
    end = time()
    print('='*40)
    print("start time is ", start*1000)
    print("end   time is ", end*1000)
    print("耗时:",end*1000 - start*1000,"ms")